import collections


class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        n = len(temperatures)
        out = [0] * n
        stack = collections.deque([0])
        for i in range(1, n):
            if temperatures[i] > temperatures[stack[-1]]:
                while stack and temperatures[i] > temperatures[stack[-1]]:
                    index = stack.pop()
                    out[index] = i - index
                stack.append(i)
            else:
                stack.append(i)
        while stack:
            index = stack.pop()
            out[index] = 0
        return out


data = Solution()
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
print(data.dailyTemperatures(temperatures))
temperatures = [30, 40, 50, 60]
print(data.dailyTemperatures(temperatures))
temperatures = [30, 60, 90]
print(data.dailyTemperatures(temperatures))
temperatures = [30, 30, 20, 50, 50, 90]
print(data.dailyTemperatures(temperatures))